#define _CRT_SECURE_NO_WARNINGS 1
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
#define inf 2147483647
const int N = 1e4 + 10;
int n, m, s;
int d[N], vis[N];

struct edge { int v, w; };
vector<edge> e[N];

void dijkstra(int s) {
	for (int i = 0; i <= n; i++) d[i] = inf;
	d[s] = 0;
	for (int i = 1; i < n; i++) {
		int u = 0;
		for (int j = 1; j <= n; j++) {
			if (!vis[j] && d[j] < d[u]) u = j;
		}
		vis[u] = 1;
		for (auto x : e[u]) {
			int v = x.v, w = x.w;
			if (d[u] + w < d[v]) d[v] = d[u] + w;
		}
	}
}

int main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cin >> n >> m >> s;
	for (int i = 0; i < m; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		e[a].push_back({ b,c });
	}
	dijkstra(s);
	for (int i = 1; i <= n; i++) cout << d[i] << " ";
	return 0;
}